1. Field of the Invention
The present invention relates to the field of computer networking, specifically to the field of asynchronous transfer mode (ATM) communications. More specifically, the present invention relates to methods and apparatus for providing topology discovery in an ATM network over a virtual service path (VSP).
2. Description of the Related Art
The present invention relates to the field of ATM and similar networking systems. Such systems are characterized by use of high-speed switches which act to switch message cells of a fixed size and format through the network. Below is provided a general description of ATM networks
ATM Networks
The described embodiment is implemented in an asynchronous transfer mode (ATM) network. Such networks are well-known in the an and, in fact, are described in various references. One such reference is Handel, R. and Huber, M. N., Integrated Broadband Networks, an Introduction to ATM-based Networks, published by Addison-Wesley Publishing Company, 1991 and hereinafter referred to as the Handel et al. reference. Another such reference is de Prycher, M., Asynchronous Transfer Mode solution for broadband ISDN, published by Ellis Horwood Limited, West Sussex, England, 1991.
Importantly, in ATM networks information is communicated in fixed-size cells which comprise a well-defined and size-limited header area and user information area. The switch fabric of an ATM switch is designed to act upon information in the header area in order to provide for muting of cells in the network. The switch fabric is normally implemented in hardware, for example using large-scale integrated circuits, in order to provide for high-speed switching of cells in the network.
Standards have been adopted for ATM networks, for example, by the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT standards require a header area comprising a fixed set of fields and being of a fixed size and a payload area, also referred to as a user information area, and also of a fixed size but allowing user-defined information fields. The CCITT standards define the header to be of a very limited size to keep at a minimum overhead associated with each cell.
ATM Cell Format
In an ATM network, all information to be transferred is packed into fixed-size slots which are commonly referred to as cells. Of course, such fixed-size slots may be referred to with other terminology, for example, packets. In one standard ATM format (CCITT Recommendation I.150, "B-ISDN ATM Functional Characteristics", Geneva, 1991), the format is generally shown in FIG. 1(a) and includes a 5-byte (also called octet) header field 101 and a 48-byte information field 102. The information field is defined by the standard to be available to the user and the header field is defined by the standard to carry information pertaining to ATM functionality, in particular, information for identification of the cells by means of a label. See, Handel et al., at pages 14-17.
The standardized format for the header field 101 is better shown in FIGS. 1(b) and 1(c) and is described in greater detail with reference to Handel et al., at pages 84-91. The header field 101 will be discussed in greater detail below; however, it is worthwhile mentioning here that the header field 101 comprises two fields: (1) a virtual channel identifier (VCI) and (2) a virtual path identifier (VPI). The VPI field is defined as an eight-bit field in one format (see FIG. 1(b)) and as a twelve-bit field in another format (see FIG. 1(c)) and is defined to be used for routing of the cell. The VCI field is also used for routing in the defined format and is defined as a sixteen-bit field.
The de Prycher reference further describes the format of the ATM cell, for example at pages 55-124 and, especially at pages 106-108.
ATM Switching
Two primary tasks are accomplished by an ATM switch: (1) translation of VPI/VCI information and (2) transport of cells from the input port to the correct output port. The functions of an ATM switch are more fully described in Handel et al. at pages 113-136.
A switch is typically constructed of a plurality of switching elements which act together to transport a cell from the input of the switch to the correct output. Various types of switching elements are well-known such as matrix switching elements, central memory switching elements, bus-type switching elements, and ring-type switching elements. Each of these are discussed in greater detail in the Handel et al, reference and each carries out the above-mentioned two primary tasks.
Translation of the VPI/VCI information is important because in a standard ATM network the contents of these fields only has local meaning (i.e., the same data would be interpreted differently by each switch). Thus, the VPI/VCI information is translated by each switch and changed prior to the cell being output from the switch. This translation is accomplished through use of translation tables which are loaded into the switch fabric, generally under control of a switch controller.
ATM Service Providers
An ATM network typically includes at least one service provider whose function it is to provide various services to devices in the network. These services may include, for example, support of a meta-signalling channel specified by the CCITT standard (channel having a VPI:VCI value of 0:1) and supervisory and configuration management functions for internal operations of the devices and for reporting of status of the devices to the service provider.
The various devices (e.g., switches and clients) are interconnected in the network through external ports on the various switches. In the network, these external ports are the lowest addressable unit addressable by the service provider. Importantly, each of the various devices in the network must communicate with the service provider during operation of the network. The communication between the devices and the service provider may be viewed as system overhead and, although necessary, such overhead should be minimized. One area in which an overhead penalty may be paid is in set-up and tear down of communications links between the various devices and the service providers. Typically, it is required to set up at least one communication link per active port. Another area of significant resource overhead is the allocation of VPI/VCI translation table entries and bandwidth utilization on the physical links. For example, each time a communication link is set-up or torn down, translation tables in each switch involved in the communication link must be allocated and updated. Updating of the translation tables and other types of allocation overhead, of course, requires system resources which could be better spent on providing user communication in the network.
Topology Discovery
Topology discovery and, in fact, automatic topology discovery is known in the field of computer networking. For example, U.S. patent Ser. No. 07/526,567 titled "Apparatus and Method for Monitoring the Status of a Local Area Network" filed May 21, 1990, hereinafter the '567 application, which application is assigned to the assignee of the present invention, describes an inventive automatic topology discovery system.
Topology discovery relates generally to the area of obtaining information on devices (e.g., switches, hubs, repeaters, bridges, etc.) in a network and reporting the information in some form such as by display of a graphical representation of the network on a display device.
The following United States Patents are also understood to relate to the area of topology discovery:
______________________________________ U.S. Issue Pat. No. Date Title ______________________________________ 4,545,013 10/1/85 Enhanced Communications Network Testing and Control System 4,644,532 2/17/87 Automatic Update of Topology in a Hybrid Network 4,827,411 5/2/89 Method of Maintaining a Topology Database 5,049,873 9/17/91 Communications Network State and Topology Manager 5,101,348 3/31/92 Method of Reducing the Amount of Information included in Topology Database Update Messages In a Data Communications Network ______________________________________
Importantly, although each of these references relate to the area of topology discovery, the references do not approach the difficult issues raised by ATM networks when attempting to provide for topology discovery.
Certain prior an topology discovery methods utilize a process of flooding of topology information within the network. In such systems, each device transmits on each of its links link state information to each of its neighbors and each of its neighbors, in turn, transmit the message to each of its own neighbors. In this manner, eventually, the entire network topology can be computed at each device in the network. It will be readily seen that in such systems, the use of a flooding technique can lead to infinite loops, in the absence of some control. Further, even with such control, a large number of messages are generated.
In addition, certain prior an topology discovery methods require some intervention, knowledge or processing power on the part of the "neighbor" switches when topology information is advertised. Of course, this has obvious performance implications.
It is also noted that in certain prior art topology discovery methods, topology information is transmitted in the form of messages to, for example, a central management unit which is capable of receiving, storing and displaying the topology information. In such systems, the topology message may be altered, to include additional information on the transmission path, as it is transmitted from device to device until it finally reaches the central management unit. In such systems, the topology message length is dependent on the number of hops between the originally transmitting device and the central manager or on the number of nodes in the network or on the number of neighbor nodes. Of course, in systems, such as ATM systems, offering a limited message size per transmitted cell, this offers disadvantages.
Dynamic client discovery
Devices (e.g., computers, work stations, printers, facsimiles, telephones, modems, etc.) need a method of identifying other devices in the network. As a matter of terminology herein, such devices will generally be referred to as clients. A client may generally be referred to in one of two ways: (1) by what the client is, and (2) by where the client is. In identifying the client "by what it is", it is known to identify the client, for example, by a logical address or by a physical address. Examples of logical addresses are IP addresses, DECnet addresses, AppleTalk addresses, etc. Examples of hardware addresses are the ATM adapter card physical address or a hardware address on an Ethernet interface card. In identifying a client by "where it is", the client may be identified by where it attaches to the network, for example by the switch number and port number (in a multi-domain network, the switch number may in fact comprise a domain number and a switch identifier.)
Importantly, in the "by where it is" approach, although relatively simple, a disadvantage is offered in that clients have to know about other clients in terms of a generally proprietary, location dependent, addressing scheme. In an ATM network, this may require preconfiguration of equipment at user's sites. In addition, if a client is moved from one switch/port to another, its address changes and this information must be conveyed to all of the other clients. This approach is, of course, time consuming and unduly restrictive.
Addressing based on a client's hardware address allows a client to move from one switch/port to another. However, some form of re-registration must occur after each move, such as with a central manager in order for other clients to be able to find the client after a move. Further, use of hardware addresses may not always be acceptable because different types of devices may have different formats of hardware addresses. Thus, interoperability is an issue.
Logical addresses supplied by the client may also present interoperability problems.
It might be noted that in certain prior an non-shared media, like a PBX, a telephone network, or the like, the location of a client is preconfigured. For example, a telephone number is allocated to a fixed location. In addition, callers must address each other using telephone numbers as the network assigned address.
In contrast, it is important in appreciating the described system to recognize that it will be advantageous to allow users to dynamically move devices from location to location in the network while still allowing communication with those devices over the network.
Formation of Client Hunt Groups
Prior art telephone systems have utilized a concept which is often referred to as "hunt groups" in which a single telephone number may be dialed by a user and the telephone system provides for access to devices (e.g., telephones, facsimile machines, etc.) at any of a number of telephone numbers or telephone extensions. For example, an office environment may have three facsimile machines due to the volume of facsimile messages received. However, it may wish to advertise only one facsimile number. In this case, a hunt group may be establised where the first facsimile machine may be connected to a telephone line which is assigned the number 555-1111, a second telephone facsimile machine is connected to a telephone line which assigned the number 555-1112 and the third telephone facsimile machine is connected to a telephone line which is assigned the number 555-1113. In this case, the company may advertise, for example, the number 555-1111. If a caller dials 555-1111 and the first facsimile machine is busy, for example sending a facsimile message, the call is automatically muted to the next telephone number in the hunt group, e.g., 555-1112, and is therefore received by the second facsimile machine.
As one aspect of the described embodiment, use of hunt groups is extended to local area networks and, in particular, to ATM local area networks. Further, devices are able to address hunt groups based on logical addresses as well as network assigned physical addresses. Still further, prior an hunt group applications are understood to provide for relatively static set-up of hunt groups. As another aspect of the described system, devices may dynamically join and withdraw from hunt groups. These aspects of the described system will be described in greater detail below.
Bootstrapping
Many prior art networking systems require downloading of bootstrapping code prior to allowing a device in a network to become fully operational. For example, in certain prior art systems, the bootstrap code is downloaded from a neighbor switch. However, in such implementations, difficulties are presented if there are hardware or other incompatibilities between the bootstrapping switch and its neighbor.
Further, networking systems may be implemented in which a neighbor switch processes and forwards bootstrap requests and bootstrap code between the bootstrapping device and a boot server. However, difficulties exist in designing such systems at least in that there is requirement to provide for processing of the packets as they are passed through the neighbor and any intermediate nodes between the bootstrapping switch and the boot server.
In one aspect of the described embodiment, these difficulties are overcome in utilizing a method and apparatus that will be described in greater detail below.
It is worthwhile making of record the following papers which describe bootstrapping methods and related materials:
(1) Bootstrapping Protocol, Croft & Gilmore, September, 1985, RFC 951, Network Working Group, IEEE; PA1 (2) Bootstrap Loading Using TFTP, Finlayson, June 1984, RFC 906, Network Working Group, IEEE; and PA1 (3) The TFTP Protocol (Version 2), Sollins, June 1981, RFC 783, Network Working Group, IEEE.
Virtual Service Paths
As will be described in greater detail below, the described embodiment takes advantage of use of virtual service paths in implementing its automatic topology discovery method and apparatus. Virtual service paths have been previously described in U.S. patent application Ser. No. 07/959,732 titled "Multiplexing of Communications Services on a Virtual Service Path in an ATM Network or the like" (the '732 application) which is assigned to the assignee of the present invention and of which this application is a continuation-in-part.